#include"../include/parsing_opg.h"

noterminal* check_noterminal(char ch, noterminal* h_noter) {
	int sign = 0;
	noterminal* h_n = h_noter;
	while (h_n->next != NULL)
	{
		h_n = h_n->next;
		if (h_n->ch == ch) {
			sign = 1;
			break;
		}
	};
	if (sign == 0) return NULL;
	else return h_n;
}

terminal* check_terminal(char ch, terminal* h_ter) {
	int sign = 0;
	terminal* h_n = h_ter;
	while (h_n->next != NULL)
	{
		h_n = h_n->next;
		if (h_n->ch == ch) {
			sign = 1;
			break;
		}
	};
	if (sign == 0) return NULL;
	else return h_n;
}

bool in_char(char* string, char ch) {
	int coutn = strlen(string);
	int i = 0;
	for (; i < coutn; i++) {
		if (string[i] == ch) break;
	}
	return coutn == i ? false : true;
}

int combin(char* ch, char* bech) {
	int cont = strlen(ch);
	int sign = 0;
	for (int i = 0; bech[i] != 0; i++) {
		if (bech[i] != '$' && !in_char(ch, bech[i])) {
			ch[cont++] = bech[i];
			sign = 1;
		}
	}
	return sign;
}

void free_list(noterminal* h_noter, terminal* h_ter) {
	noterminal* noter = h_noter;
	terminal* ter = h_ter;
	while (h_noter != NULL) {
		h_noter = h_noter->next;
		free(noter);
		noter = h_noter;
	}
	while (h_ter != NULL) {
		h_ter = h_ter->next;
		free(ter);
		ter = h_ter;
	}
}

void read_rule(char* rulefile, noterminal* h_noter, terminal* h_ter) {
	FILE* yuan = NULL;
	noterminal* noter, * r_noter = h_noter;
	terminal* ter, * r_ter = h_ter;
	//非终结符加入'#'
	ter = (terminal*)malloc(sizeof(terminal));
	ter->ch = '#';
	ter->number = 0;
	ter->next = NULL;
	r_ter->next = ter;
	r_ter = ter;
	char ch;
	int size = 1; //终结符个数
	if (fopen_s(&yuan, rulefile, "r") != 0) {
		printf("规则 文件打开失败！");
		exit(1);
	}
	while ((ch = fgetc(yuan)) != -1) {
		if (64 < ch && ch < 91) {
			noterminal* h_n = check_noterminal(ch, h_noter);
			//增加非终结符结点
			if (h_n == NULL) {
				noter = (noterminal*)malloc(sizeof(noterminal));
				noter->ch = ch;
				noter->next = NULL;
				noter->FirstVt = NULL;
				noter->Lastvt = NULL;
				noter->size = 0;
				r_noter->next = noter;
				r_noter = noter;
			}
			else {
				noter = h_n;
			}
			//读取产生式
			char chsh[10];
			for (int i = 0; i < 2; i++) ch = fgetc(yuan);
			int quit = 0;
			while ((ch = fgetc(yuan))) {
				if (ch == '|' || ch == '\n' || ch == -1) {
					//存储产生式
					chsh[quit] = '\0';
					quit = 0;
					noter->guize[noter->size++] = (char*)malloc(sizeof(char[10]));
					int s = 0;
					do {
						noter->guize[noter->size - 1][s] = chsh[s];

					} while (chsh[s++] != '\0');
					if (ch == '\n' || ch == -1) {
						break;
					}
				}
				else {
					chsh[quit++] = ch;
					//增加终结符
					if (ch < 65 || ch>90) {
						terminal* h_t = check_terminal(ch, h_ter);
						if (h_t == NULL) {
							ter = (terminal*)malloc(sizeof(terminal));
							ter->ch = ch;
							ter->next = NULL;
							ter->number = size;
							r_ter->next = ter;
							r_ter = ter;
							size++;
						}
					}
				}
			}
		}
		else {
			printf("产生式错误");
		}
	}
	//初始化优先关系表
	ter = h_ter;
	while (ter->next != NULL) {
		ter = ter->next;
		ter->patable = (char*)malloc(size+1);
		for (int i = 0; i < size; i++) ter->patable[i] = ' ';
		ter->patable[size] = 0;
	}
	fclose(yuan);
}

void make_firstvt(noterminal* h_noter,terminal* h_ter) {
	int sign = 0;
	char ch;
	noterminal* noter = h_noter;
	do {
		noter = h_noter;
		sign = 0;
		//循环终结符
		while (noter->next != NULL) {
			noter = noter->next;
			//初始化
			if (noter->FirstVt == NULL) {
				noter->FirstVt = (char*)malloc(sizeof(char[20]));
				for (int i = 0; i < 20; i++) noter->FirstVt[i] = 0;
			}
			//循环每个终结符的产生式
			for (int i = 0; i<noter->size; i++) {
				ch = noter->guize[i][0];
				//为终结符
				if (ch < 63 || ch>90) {
					if (!in_char(noter->FirstVt, ch)) {
						noter->FirstVt[strlen(noter->FirstVt)] = ch;
						sign = 1;
					}
				}
				//为非终结符
				else {
					noterminal* r_noter = check_noterminal(ch, h_noter);
					if (r_noter->FirstVt != NULL) {
						sign += combin(noter->FirstVt, r_noter->FirstVt);
					}
					ch = noter->guize[i][1];
					if (ch < 63 || ch>90) {
						if (!in_char(noter->FirstVt, ch) && ch !=0) {
							noter->FirstVt[strlen(noter->FirstVt)] = ch;
							sign = 1;
						}
					}
					else {
						error_treat(h_noter,h_ter);
					}
				}
			}
		}
	} while (sign);
	//输出firstvt
	noter = h_noter;
	printf("FIRSTVT集：\n");
	while (noter->next != NULL) {
		noter = noter->next;
		printf("Firstvt(%c)={%s}\n",noter->ch, noter->FirstVt);
	}
    printf("\n");
}

void make_lastvt(noterminal* h_noter, terminal* h_ter) {
	int sign = 0;
	char ch;
	noterminal* noter = h_noter;
	do {
		noter = h_noter;
		sign = 0;
		//循环终结符
		while (noter->next != NULL) {
			noter = noter->next;
			//初始化
			if (noter->Lastvt == NULL) {
				noter->Lastvt = (char*)malloc(sizeof(char[20]));
				for (int i = 0; i < 20; i++) noter->Lastvt[i] = 0;
			}
			//循环每个终结符的产生式
			for (int i = 0; i < noter->size; i++) {
				ch = noter->guize[i][strlen(noter->guize[i]) - 1];
				//为终结符
				if (ch < 63 || ch>90) {
					if (!in_char(noter->Lastvt, ch)) {
						noter->Lastvt[strlen(noter->Lastvt)] = ch;
						sign = 1;
					}
				}
				//为非终结符
				else {
					noterminal* r_noter = check_noterminal(ch, h_noter);
					if (r_noter->Lastvt != NULL) {
						sign += combin(noter->Lastvt, r_noter->Lastvt);
					}
					if (strlen(noter->guize[i]) == 1) continue;
					ch = noter->guize[i][strlen(noter->guize[i]) - 2];
					if (ch < 63 || ch>90) {
						if (!in_char(noter->Lastvt, ch)) {
							noter->Lastvt[strlen(noter->Lastvt)] = ch;
							sign = 1;
						}
					}
					else {
						error_treat(h_noter,h_ter);
					}
				}
			}
		}
	} while (sign);
	//输出Lastvt
	noter = h_noter;
	printf("LASTVT集：\n");
	while (noter->next != NULL) {
		noter = noter->next;
		printf("Lastvt(%c)={%s}\n",noter->ch, noter->Lastvt);
	}
    printf("\n");
}

void make_patable(noterminal* h_noter, terminal* h_ter) {
	noterminal* noter = h_noter,*r_noter;
	terminal* ter1, * ter2;
	while (noter->next != NULL) {
		noter = noter->next;
		for (int i = 0; i < noter->size; i++) {
			for (int j = 0; j < strlen(noter->guize[i])-1; j++) {
				if (noter->guize[i][j] < 63 || noter->guize[i][j]>90) {
					ter1 = check_terminal(noter->guize[i][j],h_ter);
					if (noter->guize[i][j + 1] < 63 || noter->guize[i][j + 1]>90) {
						ter2 = check_terminal(noter->guize[i][j + 1], h_ter);
						if (ter1->patable[ter2->number] != ' ') 
							error_treat(h_noter,h_ter);
						ter1->patable[ter2->number] = '=';
					}
					else {
						r_noter = check_noterminal(noter->guize[i][j + 1], h_noter);
						for (int q = 0; q < strlen(r_noter->FirstVt); q++) {
							ter2 = check_terminal(r_noter->FirstVt[q], h_ter);
							if (ter1->patable[ter2->number] != ' ')
								error_treat(h_noter,h_ter);
							ter1->patable[ter2->number] = '<';
						}
						if (j < strlen(noter->guize[i]) - 2 && (noter->guize[i][j + 2] < 63 || noter->guize[i][j + 2]>90)) {
							ter2 = check_terminal(noter->guize[i][j + 2],h_ter);
							if (ter1->patable[ter2->number] != ' ') 
								error_treat(h_noter,h_ter);
							ter1->patable[ter2->number] = '=';
						}
					}
				}
				else {
					if (noter->guize[i][j + 1] < 63 || noter->guize[i][j + 1]>90) {
						ter1 = check_terminal(noter->guize[i][j + 1], h_ter);
						r_noter = check_noterminal(noter->guize[i][j], h_noter);
						for (int q = 0; q < strlen(r_noter->Lastvt); q++) {
							ter2 = check_terminal(r_noter->Lastvt[q], h_ter);
							if (ter2->patable[ter1->number] != ' ') 
								error_treat(h_noter,h_ter);
							ter2->patable[ter1->number] = '>';
						}
					}
					else {
						error_treat(h_noter,h_ter);
					}
				}
			}
		}
	}
	//初始化'#'关系表
	noter = h_noter->next;
	ter1 = h_ter->next;
	for (int e = 0; e < strlen(noter->FirstVt); e++) {
		ter2 = check_terminal(noter->FirstVt[e], h_ter);
		ter1->patable[ter2->number] = '<';
	}
	for (int e = 0; e < strlen(noter->Lastvt); e++) {
		ter2 = check_terminal(noter->Lastvt[e], h_ter);
		ter2->patable[ter1->number] = '>';
	}
	ter1->patable[0] = '=';
	//输出优先关系表
	printf("优先关系表：\n%-10c",' ');
	terminal* ter = h_ter;
	while (ter->next != NULL) {
		ter = ter->next;
		printf("%-10c", ter->ch);
	}
	ter = h_ter;
	int size = strlen(ter->next->patable);
	while (ter->next != NULL) {
		ter = ter->next;
		printf("\n\n");
		printf("%-10c", ter->ch);
		for (int w = 0; w < size; w++) {
			printf("%-10c", ter->patable[w]);
		}
	}
	printf("\n");
}

void error_treat(noterminal* h_noter,terminal* h_ter) {
	printf("\033[31m-----------------此文法不是算符优先文法-----------------\033[0m\n");
	free_list(h_noter, h_ter);
	exit(-1);
}
char guiyue(char* st, noterminal* h_noter) {
	noterminal* noter = h_noter;
	while (noter->next != NULL) {
		noter = noter->next;
		for (int i = 0; i < noter->size; i++) {
			int le = strlen(noter->guize[i]);
			char a;
			int e = 0;
			for (; e <= le; e++) {
				a = noter->guize[i][e];
				if (a > 62 && a < 91) {
					if (st[e] > 62 && st[e] < 91)continue;
					else break;
				}
				else {
					if (st[e] == a)continue;
					else break;
				}
			}
			if (e == le + 1) return noter->ch;
		}
	}
	return 0;
}

int sf_analyse(noterminal* h_noter, terminal* h_ter, char* st) {
	printf("\n\033[33m=============================分隔符========================================\033[0m\n");
	printf("分析步骤表：\n");
	printf("步骤           分析栈          关系            输入串          动作\n");
	char anal[200] = {0}; //分析栈
	int topa = 0; 
	anal[topa++] = '#';

	char rela[200] = { 0 }; //关系栈
	int topr = 0;
	rela[topr++] = '#';
	// st[strlen(st) + 1] = 0; //输入串
	// st[strlen(st)] = '#';
    // 直接修改字符串字面量会导致未定义行为！
    // 必须创建新副本：
    size_t len = strlen(st);
    char* new_st = malloc(len + 3);
    if (new_st != NULL) {
        strcpy(new_st, st);
        new_st[len] = '#';
        new_st[len + 1] = 0;
        // 使用 new_st 替换原 st，并确保释放旧内存（如果动态分配）
        // free(st);  // 仅当 st 是动态分配时才可调用
        st = strdup(new_st);
    }
	int tops = 0;
	char a;
	terminal* ter1, * ter2;
    int idx=1;
    
	while (true)
	{
		//取出输入串字符
		a = st[tops];
		//st[tops++] = ' ';
		int j;
		//取出分析栈第一个终结符
		if (anal[topa - 1] < 63 || anal[topa - 1]>90) j = topa - 1;
		else j = topa - 2;
		//动作判断和处理
		ter1 = check_terminal(anal[j], h_ter);
		ter2 = check_terminal(a, h_ter);
		if (ter2 == NULL) {
			rela[topr++] = '?';
			rela[topr++] = a;
			printf("%-15d%-15s %-15s %-15s 无优先关系\n", idx++,anal, rela, st);
			return 0;
		}
		char re = ter1->patable[ter2->number];
		//接受
		if (a == '#' && anal[j] == '#') {
			rela[topr++] = '=';
			rela[topr++] = '#';
			printf("%-15d%-15s %-15s %-15s 接受\n", idx++,anal, rela, st);
			return 1;
		}
		//小于或等于-移进
		if (re == '<'|| re == '=') {
			rela[topr++] = re;
			rela[topr++] = a;
			printf("%-15d%-15s %-15s %-15s 移进\n", idx++,anal, rela, st);
			anal[topa++] = a;
			st[tops++] = ' ';
		}
		//大于-归约
		else if (re == '>') {
			rela[topr++] = re;
			rela[topr++] = a;
			printf("%-15d%-15s %-15s %-15s ", idx++,anal, rela, st);
			//归约串提取
			char gy[10] = { 0 };
			char w;
			int p = 1; //关系栈变数
			terminal* m1, * m2;
			do {
				w = anal[j];
				p++;
				if (anal[j - 1] < 63 || anal[j - 1] > 90)j--;
				else j -= 2;
				m1 = check_terminal(anal[j], h_ter);
				m2 = check_terminal(w, h_ter);
			} while (m1->patable[m2->number] != '<');
			for (int e = j + 1; e < topa; e++) {
				gy[e - j - 1] = anal[e];
				anal[e] = 0;
			}
			//归约
			char n = guiyue(gy, h_noter);
			if(n ==0){
				printf("无匹配产生式\n");
				return 0;
			}
			topa = j + 1;
			anal[topa++] = n;
			for (int r = 0; r < 2 * p; r++)rela[(topr--) - 1] = 0;
			printf("归约\n");
		}
		//无关系
		else {
			rela[topr++] = '?';
			rela[topr++] = a;
			printf("%-15d%-15s %-15s %-15s 无优先关系\n", idx++,anal, rela, st);
			return 0;
		}
	}
}

void to_parsing_opg(void *self,char *st){
    Parsing_OPG *p=(Parsing_OPG*)self;
	//对输入符号串进行分析
	int sign = sf_analyse(p->h_noter, p->h_ter, st);
	if (sign == 0) printf("非法输入！\n\n");
	// free_list(p->h_noter, p->h_ter);
	return;
}

Parsing_OPG *parsing_opg(char*rulefile){
    Parsing_OPG *p = malloc(sizeof(Parsing_OPG)); 
	printf("周大伟_实验3.c\n");
    printf("\033[34m魔术时间开始了！！！\033[0m\n");
    printf("==================================\n");
    p->h_noter = (noterminal*)malloc(sizeof(noterminal));
	p->h_noter->next = NULL;
	p->h_noter->FirstVt = NULL;
	p->h_noter->Lastvt = NULL;
	p->h_noter->size = 0;
	p->h_ter = (terminal*)malloc(sizeof(terminal));
	p->h_ter->next = NULL;
    p->rulefile = strdup(rulefile);
    p->to_parsing=to_parsing_opg;
	//读取文法
	read_rule(p->rulefile, p->h_noter, p->h_ter);
	//求firstvt集
	make_firstvt(p->h_noter, p->h_ter);
	//求lastvt集
	make_lastvt(p->h_noter, p->h_ter);
	//求算法优先表
	make_patable(p->h_noter, p->h_ter);
    return p;
}